"""
寻找链表倒数第 k+1 个结点
挑战介绍
实现一个算法来寻找离链表最后一个结点 k 个距离的结点，即链表倒数第 k+1 个结点，并得到此结点的数据元素。

挑战内容
本次挑战中，你需要在 kth_to_last.py 文件中补充函数 kth_to_last_elem 的空缺部分。

MyLinkedList 类继承“实现链表类”挑战中的 LinkedList 类。
MyLinkedList 类的 kth_to_last_elem 方法用于寻找离链表最后一个结点 k 个距离的结点，参数 k 用于指定距离，它需要返回结点的数据元素。
如果链表没有结点，则返回 None；如果 k 大于或等于链表的长度，也返回 None。
"""
from linked_list import LinkedList


class MyLinkedList(LinkedList):

    def kth_to_last_elem(self, k):
        if self.head is None:
            return None
        fast = self.head
        slow = self.head

        # Give fast a headstart, incrementing it
        # once for k = 1, twice for k = 2, etc
        for _ in range(k):
            fast = fast.next
            # If k >= num elements, return None
            if fast is None:
                return None

        # Increment both pointers until fast reaches the end
        while fast.next is not None:
            fast = fast.next
            slow = slow.next
        return slow.data
